1. Field of the Invention
The present invention relates to network routers, and, more particularly, to a method and apparatus for redistributing routing changes between routing protocols and other processes running on a router.
2. Description of the Related Art
As the amount of information carried by today""s networks continues to increase, ways of improving the scaleability and efficiency of network elements becomes increasingly important. Such efficiency and scaleability is of particular importance in network elements through which large amounts of network traffic must pass. One such network element is the router, a device that directs network traffic between hosts. Routers build routing tables that contain their collected information on the paths to destinations that the router knows how to reach. Routers both announce and receive route information to and from other routers. This information goes into the router""s routing table. Routers develop a hop-by-hop mechanism by keeping track of the xe2x80x9cnext hopxe2x80x9d information that enables a data packet to find its destination through the network. A router that does not have a direct physical connection to the destination of the information being routed resorts to the local routing table and forwards the information to another router that is closer to the desired destination. This process repeats itself until the information works its way through the network to the desired destination.
A router can employ several different protocols in supporting the routing of information through the network. These routing protocols can generally be divided into interior gateway protocols (IGPs), such as the router information protocol (RIP), the interior gateway routing protocol (IGRP), the enhanced interior gateway routing protocol (EIGRP), the open shortest path first (OSPF) protocol, and the intermediate system-to-intermediate system (ISIS) protocol, within their boundaries, and interconnect via an exterior gateway protocol (EGP) such as the border gateway protocol (BGP), among other such protocols.
FIG. 1 illustrates an exemplary software architecture 100 of the prior art. Included in software architecture 100 is a router operating system 110 that supports the operation of the router (not shown) on which software architecture 100 is implemented. Software modules running on router operating system 110 include routing protocols 120(1)-(N) and a routing table module 130. Routing table module 130 includes a routing table 140, as shown in FIG. 1. Routing protocols 120(1)-(N) include IGPs, such as RIP, IGRP, EIGRP, OSPF and ISIS, and EGPs such as BGP. In the router software architecture shown in FIG. 1 (software architecture 100), router operating system 110 is of a single-threaded design. As such, control passes from module to module and only one thread of execution is executed at any one time.
In such existing implementations, there exists a mechanism for the synchronous, data-driven notification of changes in the routes stored in routing table 140. This notification is passed to processes that are enabled in router operating system 110, and that may include processes such as one or more of routing protocols 120(1)-(N), maintenance processes, monitoring processes and other processes registered for notification in the event of certain changes in routing table 140. Because such processes are most commonly routing protocols (e.g., routing protocols 120(1)-(N)), such registered processes will be referred to herein under the umbrella term xe2x80x9crouting protocolsxe2x80x9d without loss of generality. The process of notification in response to a change in routing table 140 is referred to herein as route redistribution.
In router operating system 110, the notification mechanism is referred to as synchronous because the notification for a change in one or more routes (a change in routing table 140) is processed by one routing protocol before the same change notification can be delivered to another routing protocol or before another change notification for another route can be delivered. The synchronicity of this function is imposed by the single-threaded execution employed in router operating system 110. Notification in such a system may be implemented, for example, as a function callback. This means that a calling process must wait for the subroutine call to routing table module 130 to complete before the calling process can proceed. Each process requiring notification of the change to routing table 140 must be notified by routing table module 130 prior to routing table module 130 returning from the subroutine call to the calling process.
The notification mechanism is referred to herein as being data-driven to indicate a change notification is delivered to registered processes immediately upon any routing change, such as the addition, modification or deletion of a route in routing table 140. This presents the possibility of a situation in which the process updating the routing table (e.g., routing table module 130) exhibits a marked slowdown in processing due to the need to generate a large number of notifications.
The synchronous, data-driven nature of the notification mechanism also raises the problem that a routing protocol must always be prepared to accept the process change notifications. This mechanism imposes a restriction on the design and implementation of routing protocols. A more flexible approach would allow a routing protocol to accept process change notifications at its discretion, rather than at the discretion of the software module that is charged with maintaining the routing table (e.g., routing table module). A solution to this dilemma is the use of buffers. However, buffering suffers from the deficiencies noted subsequently, which are tied to the need for memory allocation and the finite resources available therefor.
In router operating system 110, change notifications are referred to herein as being selectable because a routing protocol can specify restrictions on change notifications, thereby restricting notifications of changes to those routes belonging to a specific set of one or more other routing protocols. For example, an EGP (e.g., BGP) might need to be informed of routing changes effected by an IGP (e.g., ISIS). BGP would include ISIS in the set of protocols for which BGP is to receive routing table change notifications. As the number of routing protocols is increased, the overhead of adding, modifying and deleting a route increases, particularly if a large number of the routing protocols are to receive notification of changes by a similarly large number of routing protocols. This increase in overhead is caused by the coupling between the act of making changes to routing table 140 and the need to synchronously distribute notification of that change to other of the routing protocols. As will be apparent to one of skill in the art, it is possible to restrict notifications based any number of criteria, of which restricting notifications using routing protocols is but one example.
One way to address the problems caused by this coupling is to separate the actions of updating routing table 140 and notifying routing protocols of the change. One means of effecting such a separation is through the use of buffers to hold the notifications. However, the use of buffers is not without problems. As will be appreciated by one of skill in the art, the use of buffers not only would be expected to consume memory, but in contemporary routers could be expected to consume relatively large amounts of memory (given that such routers might be expected to support over 50,000 routes in normal operation).
Another foreseeable drawback of buffers is the possibility of multiple buffering. In such a scenario, a perfect history is kept for each of the routing protocols receiving notifications of route changes in routing table 140. Because each routing protocol keeps a copy of the change history of routing table 140, large amounts of memory are consumed by the buffering of such changes. While compression techniques have been brought to bear on such problems, a satisfactory solution has not been achieved, due in part to the large number of routes that a contemporary router would be expected to support (again, on the order of over 50,000 routes). Thus, the synchronous, data-driven nature of the notification mechanism employed in contemporary router operating systems continues to impose one of the bottlenecks experienced in today""s networks.
The present invention, in various embodiments, addresses the aforementioned problems by providing a simple and efficient technique for redistributing information regarding network connections among processes using that information. By maintaining one or more entries regarding each such connection and providing an indication regarding which of those entries have been processed by a given process (or, equivalently, which entries have not been processed), the given process can determine which entries require processing without the aforementioned buffering. Moreover, by allowing such processes to update their information regarding such connections asynchronously and without the use of buffering, per se, a method and apparatus according to the present invention simplifies the distribution of such information and allows the processes to proceed at their own pace.
In one embodiment of the present invention, a method of distributing route information is described. The method includes maintaining a number of entries, indicating that at least one of the entries, requiring processing by a first process, has been processed by the first process, and causing the first process to process another of the entries requiring processing by the first process based on the indication. In doing so, the first process uses the indication to decide which of the entries requiring processing the process has already processed and which of those entries remain to be processed. Each one of the entries preferably corresponds to at least one characteristic of a network connection between a number of network elements.
In one aspect of such an embodiment, the entries are route entries, each of which corresponds to a route in a network. In another aspect of such an embodiment, the method further includes detecting a change made to the routing table by a second process, notifying the first process of the change, and updating a marker corresponding to the first process. These actions exemplify the redistribution of network information from one process to another. This can be, for example, the redistribution of routing, information from one routing protocol to another. In such an embodiment, the marker indicates which of the entries requiring processing by the first process have been thus processed.
In one aspect of such an embodiment, maintaining the route entries can include adding a route entry or modifying a route entry. A route entry may be added, for example, by adding the route entry to the route entries, and indicating that the route entry has not been processed by the process. A route entry may be modified, for example, by selecting one of the route entries, modifying information regarding a route in the network corresponding to the new route entry being modified; and indicating that the new route entry that has not been processed by the process. Indicating can include, for example maintaining a marker, corresponding to the first process, configured to indicate which of the route entries requiring processing by the first process have not been processed by the first process.
In another embodiment of the present invention, a network element is disclosed. The network element includes a processor, a memory coupled to the processor, a first process executed by the processor, a data structure having a number of entries, and a marker. In one aspect of such an embodiment, the data structure is a linked list. The marker corresponds to the first process and is configured to indicate that at least one of the entries requiring processing by the first process has been processed by the first process. The marker is also preferably configured to designate a current one of the route entries, the process having processed the current route entry and those route entries previous to the current route entry in the linked list. This can be achieved by implementing the marker as a pointer into the linked list, by adding an entry to the linked list designated as a marker, or by some other appropriate method. In an alternative aspect of this embodiment, an index is used to define which of the possible route entries are to be processed by the first process. In such an embodiment, the network element is one of a number of network elements and the data structure is stored in the memory. Preferably, each one of the entries corresponds to at least one characteristic of a network connection between certain ones of the network elements.